package com.jwetherell.my.problems.misc;

import com.jwetherell.my.Utils;

public class QuickSelect {

	private int findKthSmallestElement(int[] data, int k, int start, int end) {

		// Here j represents the index of pivot element after partitioning
		int pivotIndex = Utils.partition(data, start, end);

		if (pivotIndex == k) {
			return data[k];
		} else if (pivotIndex < k) {
			return findKthSmallestElement(data, k, pivotIndex + 1, end);
		} else
			// j>k
			return findKthSmallestElement(data, k, start, pivotIndex - 1);

	}

	public static void main(String[] args) {
		int[] input = new int[] { 9, 6, 1, 5, 4, 2 };
		int k = 4;

		QuickSelect quickSelect = new QuickSelect();

		System.out.print("Input: ");
		Utils.print(input);
		System.out.println("k: " + k);

		// Note that we are passing k-1 and not k because kth element means it
		// will be located at index k-1
		System.out.print("Output: "
				+ quickSelect.findKthSmallestElement(input, k - 1, 0,
						input.length - 1));

		System.out.print("\nData after quick select: ");
		Utils.print(input);
	}

}